273D - Dima and Figure - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=155;
const int mod=1e9+7;
int f[N][N][2][2],n,m;
signed main()
{
	cin>>n>>m;int ans=0;
	for(int i=1;i<=m;i++)for(int j=i;j<=m;j++)f[i][j][1][1]=1;
	for(int i=1;i<=n;i++)
	{
		int an=0;
		for(int l=1;l<=m;l++)for(int r=l;r<=m;r++)
		 for(int p1=0;p1<=1;p1++)for(int p2=0;p2<=1;p2++)
		  an=(an+f[l][r][p1][p2])%mod;
		ans=(ans+an*(n-i+1)%mod)%mod;
		for(int l=1;l<=m;l++)for(int r=l+1;r<=m;r++)for(int p=0;p<=1;p++)
		 f[l+1][r][0][p]=(f[l+1][r][0][p]+f[l][r][0][p]+f[l][r][1][p])%mod;
		for(int l=1;l<=m;l++)for(int r=m;r>l;r--)for(int p=0;p<=1;p++)
		 f[l][r-1][p][0]=(f[l][r-1][p][0]+f[l][r][p][1]+f[l][r][p][0])%mod;	
		for(int l=m;l>1;l--)for(int r=l;r<=m;r++)for(int p=0;p<=1;p++)
		 f[l-1][r][1][p]=(f[l-1][r][1][p]+f[l][r][1][p])%mod;
		for(int l=m;l>=1;l--)for(int r=l;r<m;r++)for(int p=0;p<=1;p++)
		 f[l][r+1][p][1]=(f[l][r+1][p][1]+f[l][r][p][1])%mod;
	}
	cout<<ans<<endl;
	return 0;
}